The present invention focuses on image processing of binary images to enable such images to be printed or otherwise displayed at an enhanced pixel resolution. It is known in the art of digital printing that it is highly desirable to print low resolution documents in an enhanced mode. Moreover, template-based binary resolution enhancement and conversion has been addressed by others such as R. Eschbach Application Ser. No. 08/169,483, H. Kang US-A-5,270,836, issued Dec. 14, 1993 and US-A-5,301,037, issued Apr. 5, 1994, and L. Mailloux US-A-5,282,057, issued Jan. 25, 1994, all of which are hereby incorporated by reference. The present invention differs from that body of work in that it is a method and apparatus directed to converting a binary image to a multiple-bit-per-pixel image while maintaining the same spatial resolution.
More closely related is the work of Banton and Charissis, in a co-pending application Ser. No. 08/241,431 filed concurrently herewith and Loce and Cianciosi in application Ser. No. 08/169,485, where binary bit maps are converted to an enhanced multibit form. Banton and Charissis focus on gray imaging of halfbits and ragged features by employing a single set of templates within a 9.times.9 window. A match in their scheme yields an output that describes how the pixel should be imaged. Several matches with different templates could occur at the same location, and when that occurs, the resulting output is decided in an arbitration circuit. Moreover, the set of templates were designed manually over a long period of time. Loce and Cianciosi proposed using a statistically generated set of templates that transformed from a binary bit map to an array of pulse-width position-modulated (PWPM) codes, where each code was that one most often observed for a given input pattern in a statistical training process.
In short, image processing in electronic printing is often called upon to take a binary bit map as input and transform it to a gray-scale image. For example, scanned documents are typically digitized at 8 bits/pixel and then thresholded to 1 bit/pixel. Converting from 1 to 2 bits per pixel for enhancement purposes is a filtering operation that estimates what the image would have been had it been converted from this 8 bit representation, or some idealized 8 bit representation, to 2 bits instead of 8 bits to 1 bit. "Descreening" a halftoned image is a 1-to-N bit filtering operation that yields an estimate of the gray-scale image prior to halftoning, or an estimate of that gray-scale image quantized in a particular manner.
Heretofore, related publications have discussed 1-to-N bit enhancement using morphological filters. For instance Loce and Dougherty, in "The Mean-Absolute-Error Theorem for Computational Morphology," Proc. SPIE, Vol. 2030, San Diego, July 1993, describe passing an input binary image through parallel morphological filters, where the output of each filter is a "gray level slice" of the total output. The output slices are then stacked to form the final multibit/pixel image. The design method requires the filters for each layer to be designed simultaneously and therefore is very complex in a combinatoric sense. Because of the extensive computation involved in evaluating the combinatorics, the filters given in the publication are limited to operate within a 5 pixel window.
Stack filters in general are described by Wendt, Coyle and Gallagher "Stack Filters," IEEE ASSP-34, no. 4, pp. 898-911, 1986, and optimization of stack filters are described by Lin and Coyle, "Stack Filters and the MAE Criterion," IEEE ASSP-36, no. 8, pp. 1244-1254, 1988. In their optimization scheme, to simplify the design process, the same filter is applied to all slices. However, this simplification renders the method ineffective for binary to gray enhancement. In another publication by Lin and Coyle, "Minimum MAE Estimation over the Class of Generalized Stack Filters," IEEE ASSP-38, no. 4, pp. 663-678, 1990, they state that they have not been able to develop an overall filter that properly stacks when each layer utilizes a different filter. Note that stack filters are typically used for filtering gray-scale images, and, other than the related computation morphology work cited above, are not believed to have been described for binary to gray scale transformation. Also note that the stacking architecture allows for certain cost savings in the electronics.
Also of interest is the publication "Computational Mathematical Morphology," by E. Dougherty and D. Sinha, University Laboratory Report MIL-92-17, Morphological Imaging Laboratory, Center for Imaging Science, Rochester Institute of Technology. This report proposes a general mathematical framework for performing a parallel/adding filtering from an arbitrary number of gray levels to another arbitrary number of gray levels, although the filter design and implementation method are not given. Also, the relationship given to combine the output of the parallel filtering does not necessarily ensure the "no gap" criterion for stacking. Furthermore, while a design method is given in the reference by Loce and Dougherty, it suffers from the described combinatoric complexity.
The present invention is directed to a new method for designing an apparatus for implementing 1-to-N bit stack filters, where the design of the filters for the individual level slices of the stack is sufficiently independent that the combinatoric complexity is greatly reduced, thereby enabling filters to be designed that employ much larger windows. For example, using this method, it is possible to design filters that employ 32 pixel windows, which pack simply into a single unsigned long integer representation on many computing platforms. When properly designed, an optimal stack filter with this large window greatly outperforms, in an output image quality sense, the small window filters described by Loce and Dougherty, in "The Mean-Absolute-Error Theorem for Computational Morphology," Proc. SPIE, Vol. 2030, San Diego, July 1993.
In accordance with the present invention, there is provided a method of transforming a plurality of rasterized binary signals indicative of a binary input image into a multiple-bit-per-pixel gray-scale image, comprising the steps of: (a) receiving the plurality of rasterized binary signals; (b) filtering the rasterized binary signals to produce a binary level slice from each one of a plurality of level slice filters; and (c) combining the binary level slices to produce the multiple-bit-per-pixel gray-scale image.
In accordance with another aspect of the present invention, there is provided a method for transforming a binary input image B(x,y), represented as a plurality of rasterized binary signals, into a multiple-bit-per-pixel gray-scale image comprising the steps of: (a) storing the binary input image B(x,y) in a first memory M(x,y); (b) filtering the binary image stored in the first memory M(x,y) to produce a filtered binary image F.sub.1 (x,y); (c) storing the filtered binary input image F.sub.1 (x,y) in the first memory M(x,y); (d) filtering the binary image stored in the first memory M(x,y) to produce a new filtered binary image F.sub.n (x,y); and (e) stacking filtered binary image F.sub.1 (x,y) and new filtered binary image F.sub.n (x,y) to produce a gray-scale output image O(x,y), wherein each of a plurality of pixels therein is represented as a two-bit value.
In accordance with yet another aspect of the present invention, there is provided a method for transforming a binary input image B(x,y) into a multiple-bit-per-pixel gray-scale image comprising the steps of: (a) storing the binary input image B(x,y) in a first memory M(x,y); (b) filtering the binary image stored in the first memory M(x,y) to produce a filtered binary image F.sub.1 (x,y); (c) storing the filtered binary input image F.sub.1 (x,y) in the first memory M(x,y); (d) filtering the binary image stored in the first memory M(x,y) to produce a new filtered binary image F.sub.n (x,y); (e) stacking filtered binary image F.sub.1 (x,y) and new filtered binary image F.sub.n (x,y) to produce interim image I(x,y), and storing the interim image in a second memory; (f) storing the new filtered binary input image F.sub.n (x,y) in the first memory M(x,y); (g) filtering the binary image stored in the first memory M(x,y) to produce a new filtered binary image F.sub.n (x,y); (h) stacking interim image i(x,y) and new filtered binary image F.sub.n (x,y) to produce a new interim image I(x,y), and storing the interim image in a second memory; and (i) repeating steps (f) through (h) above for a plurality of times to produce a gray-scale output image O(x,y), wherein each of a plurality of pixels therein is represented as a multiple-bit value.
In accordance with a further aspect of the present invention, there is provided a digital image filtering apparatus, comprising: a first memory for storing a binary input image; a first level slice filter to which the stored binary image may be applied, said first level slice filter producing a primary binary signal in response to each pixel of the binary image applied thereto to produce a first-slice filter output; combination logic for logically combining the first-slice filter output and the binary input image to produce an output image first-slice; a second level slice filter to which the output image first slice may be applied, said second level slice filter producing a secondary binary signal in response to each pixel of the output image first slice applied thereto to produce a second-slice filter output; combination logic for logically combining the second-slice filter output and the first output image slice to produce a second output image slice; and stacking logic for logically stacking the second image slice and the first image slice to produce a filtered image that is a multiple-bit per pixel image representing each of a plurality of binary pixels within the binary input image as a two-bit alue.
In accordance with another aspect of the present invention, there is provided a digital image filtering apparatus for transforming a binary input image represented as a plurality of rasterized binary signals each representing an image pixel, into a multiple-bit per pixel gray scale image, comprising: a primary level-slice filter for filtering the binary input image to produce a first filtered binary image; a first secondary level-slice filter for filtering the first filtered binary image to produce a second filtered binary image; a second secondary level-slice filter for filtering the first filtered binary image to produce a third filtered binary image; and an adder for adding the first filtered binary image, the second filtered binary image, and the third filtered binary image to produce a gray-scale output image, wherein each of a plurality of pixels therein is represented as a multiple-bit value.
In accordance with an aspect of the present invention, there is provided a digital image filtering apparatus, comprising: a first memory for storing a binary input image; an extensive level-slice filter to which the stored binary image may be applied, said first level-slice filter producing a first binary signal in response to each pixel of the stored binary image applied thereto to produce a first level slice image; an anti-extensive level-slice filter to which the stored binary image may be applied, said second level-slice filter producing a second binary signal in response to each pixel of the stored binary image applied thereto to produce a second level slice image; and stacking logic for logically stacking the second image slice and the first image slice to produce a filtered image that is a multiple-bit per pixel image representing each of a plurality of binary pixels within the binary input image as a two-bit value.
In accordance with a further aspect of the present invention, there is provided a digital image filtering apparatus for transforming a binary input image represented as a plurality of rasterized binary signals, each representing an image pixel, into a multiple-bit per pixel gray scale image, comprising: a first level-slice filter to which the binary input image may be applied, said first level-slice filter producing a first binary signal in response to each pixel of the binary image applied thereto to produce a first image slice; a second level-slice filter to which the binary input image may be applied, said second level-slice filter producing a secondary binary signal in response to each pixel of the binary image applied thereto to produce a second image slice; and an adder for adding the second image slice and the first image slice to produce a filtered image that is a multiple-bit per pixel image representing each of a plurality of pixels within the input image as a multiple-bit value.
In accordance with yet another aspect of the present invention, there is provided a method for designing a stack filter, for enhancing a binary input image into a multiple-bit-per-pixel image, comprising the steps of: (a) obtaining an idealized gray-scale image, wherein the image contains structures representative of those likely to appear in documents to be enhanced from binary to a multiple-bit per pixel gray-scale range; (b) thresholding the gray-scale image using a binary threshold level to produce a binary image; (c) thresholding the gray-scale image at a second threshold, preferably not equal to the binary threshold, to produce a first level slice; (d) producing, as a function of the binary pixel levels in the binary image and the first level slice, a first difference image; and (e) generating, as a function of the first difference image and the binary image, a first level slice filter having a plurality of templates that, upon receiving binary input signals within windowed subsets of pixel locations within the binary image will produce binary output signals equivalent to pixels at corresponding pixel positions in the first difference image.